{% extends 'c-word.html' %} {% block title %} data | structure {% endblock title %} {% block point1 %}

category: data | structure

数据结构

概述


定义

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

  • Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。
  • 而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。

B = (D, R)


B = (D, R, O)


算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。

高效的程序需要在数据结构的基础上设计和选择算法。

程序 = 数据结构 + 算法

总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体




组成

数据结点

数据结点（数据元素），简称结点（node）：
描述一个独立事物的名称、数量、特征、性质的一组相关信息组成一个数据结点；
通常，一个节点含有多个数据项（data item）
  • 结点的类型：结构型
  • 关键字（key）
单值类型的结点：只含一个数据项

数据结点间的关系集

数据结点间的运算集

前三项（查找、插入、删除）为基本运算，后六项都可以通过前三项的组合实现。
查找（search）
插入（insert）
删除（delete）
存取（access）
更新（update）
合并（merge）
分裂（split）
复制（copy）
排序（sorting）

分类



表 - 一对一

树 - 一对多

图 - 多对多

散 - 无关


研究对象

数据的逻辑结构

数据的逻辑结构是从具体问题抽象出来的数学模型，反映数据元素之间的逻辑关系，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关；是描述数据元素及其关系的数学特性的，有时就把逻辑结构简称为数据结构。
逻辑结构是在计算机存储中的映像，形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
数据结构中，逻辑上（逻辑结构：数据元素之间的逻辑关系）可以把数据结构分成线性结构和非线性结构。
  • 线性结构的顺序存储结构是一种顺序存取的存储结构；
  • 线性表的链式存储结构是一种随机存取的存储结构。线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数都无关。

数据的物理结构


指数据的逻辑结构在计算机存储空间的存放形式。 
数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与各数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。
关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系。

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

为什么要学习“数据结构”

  • 为了便于对数据进行操作以及算法的优化。
  • 从编程水平上说，知道什么是好的算法，学会设计和选择好的算法，会很大程度上提高程序设计能力和初步的算法设计能力。
  • 从能力素质培养上说，训练计算机思维能力和问题求解能力，提高认知水平。

抽象数据类型 - ADT

抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。抽象数据类型可用以下三元组表示：（D，S，P）。D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的定义为：

        ADT 抽象数据类型名：{ 数据对象：（数据元素集合），数据关系：（数据关系二元组结合），基本操作：（操作函数的罗列）}；

两个重要特性

抽象数据类型有两个重要特性：
数据抽象
用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。
数据封装
将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

数据结构的抽象和实现

数据的逻辑结构（logical form）

B = (D, R)

B = (D, R, O)

逻辑结构示例



数据的物理结构（physical form）




表结构

概述

分类

线性表

顺序表、链表、栈（顺序栈、链栈）、队（顺序队、链队）

散列表

线性表（linear list）


在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：

  • 顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。
  • 链表，将元素存放在通过链接构造起来的一系列存储块中。

实现方式

逻辑实现

D
具有 n(n >= 0) 个数据结点（元素）的序列 A = (a1, a2, ..., an)；数据集合可以为空。
R
先后次序

首结点和尾结点
表的长度
空表
前驱和后继（左邻和右邻）
有序表

O

物理实现

存储方式

顺序存储

存储结点的逻辑次序与物理次序一致。

内存中地址连续

长度不可变更

支持随机查找 可以在O(1)内查找元素

适用于需要大量访问元素的 而少量增添/删除元素的程序

特点
  • 用一组地址连续的存储单元依次存放数据元素。
  • 所有数据元素的存储位置均取决于第一个数据元素的存储位置。
适用场合
  • 表长不大
  • 不做，或很少做插/删操作
  • 只在表的端点出做插/删操作

链式存储

存储结点的逻辑次序与物理次序不一致

内存中地址非连续

长度可以实时变化

不支持随机查找 查找元素时间复杂度O（n）

适用于需要进行大量增添/删除元素操作 而对访问元素无要求的程序

顺序存储和链式存储的优缺点及适用场合

  • 顺序表：
    • （1）优点：查找速度较快，查找方便                
    • （2）缺点：动态操作困难                
    • （3）适用于查找操作 
  • 链表：
    • （1）优点：动态操作方便，方便扩展           
    • （2）缺点：查询效率低，不利于查询            
    • （3）适用于动态的删除， 插入等操作

链表失去了顺序表随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示：

操作链表顺序表
访问元素O(n)O(1)
在头部插入/删除O(1)O(n)
在尾部插入/删除O(n)O(1)
在中间插入/删除O(n)O(n)

注意虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时进行的是完全不同的操作。链表的主要耗时操作是遍历查找，删除和插入操作本身的复杂度是O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。



顺序表

线性表采用顺序存储的方式存储就称之为顺序表。
顺序表是在计算机内存中以数组的形式保存的线性表。
顺序表是指用一组地址连续的存储单元依次存储数据元素的线性结构。

顺序表的基本形式


图a表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：

Loc(ei) = Loc(e0) + c*i

故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。

如果元素的大小不统一，则须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

图b这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。


顺序表的结构


一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为实现正确操作而需记录的信息，即有关表的整体情况的信息，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

顺序表的两种基本实现方式



图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。

一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

元素存储区替换

  • 一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。
  • 分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

元素存储区扩充

采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略


一体式结构
分离式结构

操作

查找
理解查找的基本含义
写出顺序查找的算法
写出带监督元的顺序查找算法


查找（search）：给定结点值 x，查找值等于 x 的结点的存储地址。

顺序查找


顺序查找（带监督元）







二分查找算法










插入
插入（insert）：在表中添加一个新结点

如图所示，为顺序表增加新元素111的三种方式

a. 尾端加入元素，时间复杂度为O(1)

b. 非保序的加入元素（不常见），时间复杂度为O(1)

c. 保序的元素加入，时间复杂度为O(n)

删除


a. 删除表尾元素，时间复杂度为O(1)

b. 非保序的元素删除（不常见），时间复杂度为O(1)

c. 保序的元素删除，时间复杂度为O(n)

Python 中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。

tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。

list 的基本实现技术

Python标准类型list就是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有元素的顺序（即保序），而且还具有以下行为特征：

  • 基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1)；

    为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区中。

  • 允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。

    为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时list对象的标识id不变，只能采用分离式实现技术。

在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append(x) （或 list.insert(len(list), x)，即尾部插入）比在指定位置插入元素效率高的原因。

在Python的官方实现中，list实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。



链表

准确地描述表的链式存储结构
写出单向链表的指定位置插入和删除的程序段
知道链表的种类和作用
知道常用链表的特点和图示方法
能够写出单向加尾链表查找的算法
能够写出单向加头循环链表的删除算法
能够写出双向链表的插入和删除算法
能够写出构造有序链表的算法

为什么需要链表

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

定义

链表就是表头指针和一串相继链接的结点的总称。

线性表采用指针链接的方式存储就称之为链表。

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。


特点

种类


链表的图示




单向链表

定义
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置（python中的标识）
  • 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
单链表的操作
  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历整个链表
  • add(item) 链表头部添加元素
  • append(item) 链表尾部添加元素
  • insert(pos, item) 指定位置添加元素
  • remove(item) 删除节点
  • search(item) 查找节点是否存在
单链表的实现
class SingleLinkList(object):
    """单链表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None

    def length(self):
        """链表长度"""
        # cur初始时指向头节点
        cur = self._head
        count = 0
        # 尾节点指向None，当未到达尾部时
        while cur != None:
            count += 1
            # 将cur后移一个节点
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""
    def add(self, item):
        """头部添加元素"""
        # 先创建一个保存item值的节点
        node = SingleNode(item)
        # 将新节点的链接域next指向头节点，即_head指向的位置
        node.next = self._head
        # 将链表的头_head指向新节点
        self._head = node
    def append(self, item):
        """尾部添加元素"""
        node = SingleNode(item)
        # 先判断链表是否为空，若是空链表，则将_head指向新节点
        if self.is_empty():
            self._head = node
        # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            cur = self._head
            while cur.next != None:
                cur = cur.next
            cur.next = node
    def insert(self, pos, item):
        """指定位置添加元素"""
        # 若指定位置pos为第一个元素之前，则执行头部插入
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾部插入
        elif pos > (self.length()-1):
            self.append(item)
        # 找到指定位置
        else:
            node = SingleNode(item)
            count = 0
            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
            pre = self._head
            while count < (pos-1):
                count += 1
                pre = pre.next
            # 先将新节点node的next指向插入位置的节点
            node.next = pre.next
            # 将插入位置的前一个节点的next指向新节点
            pre.next = node
    def remove(self,item):
        """删除节点"""
        cur = self._head
        pre = None
        while cur != None:
            # 找到了指定元素
            if cur.item == item:
                # 如果第一个就是删除的节点
                if not pre:
                    # 将头指针指向头节点的后一个节点
                    self._head = cur.next
                else:
                    # 将删除位置前一个节点的next指向删除位置的后一个节点
                    pre.next = cur.next
                break
            else:
                # 继续按链表后移节点
                pre = cur
                cur = cur.next
    def search(self,item):
        """链表查找节点是否存在，并返回True或者False"""
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

测试

if __name__ == "__main__":
    ll = SingleLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    print "length:",ll.length()
    ll.travel()
    print ll.search(3)
    print ll.search(5)
    ll.remove(1)
    print "length:",ll.length()
    ll.travel()

单向循环链表

定义
单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为None，而是指向链表的头节点。

操作
  • is_empty() 判断链表是否为空
  • length() 返回链表的长度
  • travel() 遍历
  • add(item) 在头部添加一个节点
  • append(item) 在尾部添加一个节点
  • insert(pos, item) 在指定位置pos添加节点
  • remove(item) 删除一个节点
  • search(item) 查找节点是否存在
实现
class Node(object):
    """节点"""
    def __init__(self, item):
        self.item = item
        self.next = None


class SinCycLinkedlist(object):
    """单向循环链表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        # 如果链表为空，返回长度0
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        if self.is_empty():
            return
        cur = self._head
        print cur.item,
        while cur.next != self._head:
            cur = cur.next
            print cur.item,
        print ""


    def add(self, item):
        """头部添加节点"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            #添加的节点指向_head
            node.next = self._head
            # 移到链表尾部，将尾部节点的next指向node
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            #_head指向添加node的
            self._head = node

    def append(self, item):
        """尾部添加节点"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            # 移到链表尾部
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            # 将尾节点指向node
            cur.next = node
            # 将node指向头节点_head
            node.next = self._head

    def insert(self, pos, item):
        """在指定位置添加节点"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        """删除一个节点"""
        # 若链表为空，则直接返回
        if self.is_empty():
            return
        # 将cur指向头节点
        cur = self._head
        pre = None
        # 若头节点的元素就是要查找的元素item
        if cur.item == item:
            # 如果链表不止一个节点
            if cur.next != self._head:
                # 先找到尾节点，将尾节点的next指向第二个节点
                while cur.next != self._head:
                    cur = cur.next
                # cur指向了尾节点
                cur.next = self._head.next
                self._head = self._head.next
            else:
                # 链表只有一个节点
                self._head = None
        else:
            pre = self._head
            # 第一个节点不是要删除的
            while cur.next != self._head:
                # 找到了要删除的元素
                if cur.item == item:
                    # 删除
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # cur 指向尾节点
            if cur.item == item:
                # 尾部删除
                pre.next = cur.next

    def search(self, item):
        """查找节点是否存在"""
        if self.is_empty():
            return False
        cur = self._head
        if cur.item == item:
            return True
        while cur.next != self._head:
            cur = cur.next
            if cur.item == item:
                return True
        return False

if __name__ == "__main__":
    ll = SinCycLinkedlist()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print "length:",ll.length()
    ll.travel()
    print ll.search(3)
    print ll.search(7)
    ll.remove(1)
    print "length:",ll.length()
    ll.travel()

双向链表

定义
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。


操作
  • is_empty() 链表是否为空
  • length() 链表长度
  • travel() 遍历链表
  • add(item) 链表头部添加
  • append(item) 链表尾部添加
  • insert(pos, item) 指定位置添加
  • remove(item) 删除节点
  • search(item) 查找节点是否存在
实现
class Node(object):
    """双向链表节点"""
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None


class DLinkList(object):
    """双向链表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判断链表是否为空"""
        return self._head == None

    def length(self):
        """返回链表的长度"""
        cur = self._head
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍历链表"""
        cur = self._head
        while cur != None:
            print cur.item,
            cur = cur.next
        print ""

    def add(self, item):
        """头部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 将node的next指向_head的头节点
            node.next = self._head
            # 将_head的头节点的prev指向node
            self._head.prev = node
            # 将_head 指向node
            self._head = node

    def append(self, item):
        """尾部插入元素"""
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将_head指向node
            self._head = node
        else:
            # 移动到链表尾部
            cur = self._head
            while cur.next != None:
                cur = cur.next
            # 将尾节点cur的next指向node
            cur.next = node
            # 将node的prev指向cur
            node.prev = cur



    def search(self, item):
        """查找元素是否存在"""
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False

指定位置插入节点


    def insert(self, pos, item):
        """在指定位置添加节点"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移动到指定位置的前一个位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 将node的prev指向cur
            node.prev = cur
            # 将node的next指向cur的下一个节点
            node.next = cur.next
            # 将cur的下一个节点的prev指向node
            cur.next.prev = node
            # 将cur的next指向node
            cur.next = node

删除元素


    def remove(self, item):
        """删除元素"""
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                # 如果首节点的元素即是要删除的元素
                if cur.next == None:
                    # 如果链表只有这一个节点
                    self._head = None
                else:
                    # 将第二个节点的prev设置为None
                    cur.next.prev = None
                    # 将_head指向第二个节点
                    self._head = cur.next
                return
            while cur != None:
                if cur.item == item:
                    # 将cur的前一个节点的next指向cur的后一个节点
                    cur.prev.next = cur.next
                    # 将cur的后一个节点的prev指向cur的前一个节点
                    cur.next.prev = cur.prev
                    break
                cur = cur.next

测试

if __name__ == "__main__":
    ll = DLinkList()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print "length:",ll.length()
    ll.travel()
    print ll.search(3)
    print ll.search(4)
    ll.remove(1)
    print "length:",ll.length()
    ll.travel()





结点的产生和回收










操作

结点的链接操作


查找
单向加尾链表的查找

插入



删除




单向加头循环链表的删除


构造有序链表








栈

能够准确描述栈的特点
能够写出顺序栈的入栈和出栈算法
能够写出链栈的入栈和出栈算法
能够准确描述栈在程序中断中的作用
掌握简单算术表达式求值的方法

定义

只允许在同一端点出进行插入或删除的表结构称为栈（stack），栈是一种后进先出结构，又称为后进先出表（LIFO 表）。


术语

栈顶（top）：允许插入和删除的一端，top 指针总是指向栈顶。
栈底（bottom）：不允许插入和删除的一端。
进栈（push，压栈）：元素插入栈的过程。
出栈（pop，退栈）：从栈中弹出一个元素的过程。
栈空
栈满
栈溢出

栈的特点

后进先出，LIFO

栈的实例

子弹夹
浏览器的类似后退和前进按钮
函数之间的嵌套调用以及递归函数的执行

栈的物理实现 

顺序栈
链栈

栈的操作

  • Stack() 创建一个新的空栈
  • push(item) 添加一个新的元素item到栈顶
  • pop() 弹出栈顶元素
  • peek() 返回栈顶元素
  • is_empty() 判断栈是否为空
  • size() 返回栈的元素个数

栈的 Python 实现

class Stack(object):
    """栈"""
    def __init__(self):
         self.items = []

    def is_empty(self):
        """判断是否为空"""
        return self.items == []

    def push(self, item):
        """加入元素"""
        self.items.append(item)

    def pop(self):
        """弹出元素"""
        return self.items.pop()

    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items)-1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)

if __name__ == "__main__":
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("itcast")
    print stack.size()
    print stack.peek()
    print stack.pop()
    print stack.pop()
    print stack.pop()

栈的应用

程序中断
中断：一个程序执行期间被其他程序所打断。
断点：被打断的地方。
现场（栈架）：被打断的程序当前的执行情况。

栈架与栈架之间服从后进先出的栈原则。
同一个栈架，数据存储的次序也遵守后进先出的栈原则。
保护现场和恢复现场。
嵌套中断的现场需要层层保护。








队列

能够准确描述队列的特点
能够写出顺序对的入队和出队算法

定义

允许在一端插入、另一端删除的表叫做队，或队列。

对结构好似一端两端开口的管道，结点从一端进入，从另一端退出。

对结构遵循先进先出原则，又称先进先出表（FIFO 表）。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

术语

队尾（rear）：允许插入的一端
队头（front）：允许删除的一端
队满
队空
进队和出队：队的插入和删除

指针 first 和 last 分别指向队头和队尾，每当进队时移动尾指针，每当出队时移动首指针。


队的特点

先进先出（FIFO）

操作

  • Queue() 创建一个空的队列
  • enqueue(item) 往队列中添加一个item元素
  • dequeue() 从队列头部删除一个元素
  • is_empty() 判断一个队列是否为空
  • size() 返回队列的大小

队列的 Python 实现

class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        """进队列"""
        self.items.insert(0,item)

    def dequeue(self):
        """出队列"""
        return self.items.pop()

    def size(self):
        """返回大小"""
        return len(self.items)

if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    print q.size()
    print q.dequeue()
    print q.dequeue()
    print q.dequeue()


队的实例

排队买票

循环队（环形队 cyclic queue）

队的物理实现

顺序队
链式队

双端队列

定义

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。


操作

  • Deque() 创建一个空的双端队列
  • add_front(item) 从队头加入一个item元素
  • add_rear(item) 从队尾加入一个item元素
  • remove_front() 从队头删除一个item元素
  • remove_rear() 从队尾删除一个item元素
  • is_empty() 判断双端队列是否为空
  • size() 返回队列的大小

实现

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.items == []

    def add_front(self, item):
        """在队头添加元素"""
        self.items.insert(0,item)

    def add_rear(self, item):
        """在队尾添加元素"""
        self.items.append(item)

    def remove_front(self):
        """从队头删除元素"""
        return self.items.pop(0)

    def remove_rear(self):
        """从队尾删除元素"""
        return self.items.pop()

    def size(self):
        """返回队列大小"""
        return len(self.items)


if __name__ == "__main__":
    deque = Deque()
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print deque.size()
    print deque.remove_front()
    print deque.remove_front()
    print deque.remove_rear()
    print deque.remove_rear()





散列表

复述散列表的作用和意义
学会散列函数的设计方法
实现散列表的构造、插入和查找
选择并会使用开放地址法解决散列冲突

散列函数的设计原则


散列函数的设计方法


散列冲突






散列表的构造

树结构

概述

什么是树
树的存储方法
能够准确复述树结构的相关术语
能够用图示和 C 语言描述树结构的存储方式
二叉树的基本概念和存储方法，区别不同的二叉树
能够用 C 语言描述二叉树的双链表的存储结构
能够准确图示森林、树、二叉树的相互转换



二叉树是树结构的基础

定义

树是一种非线性的数据结构。

树是递归定义的，用来描述数据之间层次关系、分支关系和嵌套关系的基本数据结构。

术语



  • 结点的度：当前结点所具有的子树的个数
  • 树的元数：一棵树中，结点的度能允许的最大值
  • 树叶：度数为 0 的结点（也称终端结点）
  • 分枝点（内结点）：非叶结点
  • 兄弟：同父的结点互为兄弟
  • 结点的层数：根的层数定为 1；递推地，第 i 层结点的儿子层数为 i + 1
  • 结点的高度：叶的高度定为 1；递推地，非叶结点的高度等于它各个儿子高度的最大值加 1
  • 树高：等于其根结点的高度
  • 有序树：树中结点的儿子按照某种次序排列
  • 无序树：
  • 位置树：一颗有序树中规定了每个结点儿子的位置
  • 森林：树的集合，一个森林可包含 0 至多棵树

特点

  • 每个节点有零个或多个子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；

树的种类

  • 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
  • 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
    • 二叉树：每个节点最多含有两个子树的树称为二叉树；
      • 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
      • 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
      • 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
    • 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
    • B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。


树的表示方法

 

常见的一些树的应用场景

1.xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
2.路由协议就是使用了树的算法
3.mysql数据库索引
4.文件系统的目录结构
5.所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构

树的存储方法

顺序存储

顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

链式存储


由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2




计算机中树的存储方法

多重链接




儿子兄弟链




父亲链域



二叉树

定义

二叉树也称二分树，也称二元位置树：每个结点最多 2 个儿子，称为左、右儿子。

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

五种基本形态


二叉树的性质

性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i>0）
性质2: 深度为k的二叉树至多有2^k - 1个结点（k>0）
性质3: 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)
性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

二叉树的存储


静态存储 -- 顺序顺序法

补齐为完全二叉树，然后在按完全二叉树的存储方法存储

动态存储 -- 双链法






分类

满二叉树

满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。




完全二叉树

完全二叉树是满二叉树的一部分；
满二叉树是完全二叉树的特例

完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。









非完全二叉树

补齐为完全二叉树，然后在按完全二叉树的存储方法存储


普通树与二叉树的相互转换

将复杂树的问题转换为简单二叉树的问题 -- 化繁为简

将树转换为二叉树





树中每个结点指向最左儿子的边不变


添加边，链接其紧挨着的第一个兄弟


去掉除链接的最左儿子的其余儿子的边，然后顺时针旋转 45度，即可得到二叉树

将二叉树转换为树

树转换为二叉树的逆过程

注意：
要转换为树的二叉树，其根结点没有右子树

森林与二叉树的转换

可以借助树与二叉树的转换来实现

森林转换为二叉树


二叉树转换为森林


二叉树的运算

遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
深度优先遍历（递归）
对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。



先根遍历

中根遍历

后根遍历






广度优先遍历（队列，层次遍历）
从树的root开始，从上到下从从左到右遍历整个树的节点



查找 - 递归遍历

二叉树的构造

能够准确判断二叉树构造的唯一性条件
能够编程实现先（后）序、中序构造二叉树的递归算法
能够编程实现用扩充先序序列构造二叉树的递归算法


二叉树构造的问题











先（后）序序列、中序序列构造二叉树






扩充先（后）序序列唯一构造二叉树










二叉树的节点表示以及树的创建

通过使用Node类中定义三个属性，分别为elem本身的值，还有lchild左孩子和rchild右孩子

class Node(object):
    """节点类"""
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

树的创建,创建一个树的类，并给一个root根节点，一开始为空，随后添加节点

class Tree(object):
    """树类"""
    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        """为树添加节点"""
        node = Node(elem)
        #如果树是空的，则对根节点赋值
        if self.root == None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            #对已有的节点进行层次遍历
            while queue:
                #弹出队列的第一个元素
                cur = queue.pop(0)
                if cur.lchild == None:
                    cur.lchild = node
                    return
                elif cur.rchild == None:
                    cur.rchild = node
                    return
                else:
                    #如果左右子树都不为空，加入队列继续判断
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)




检索树

能够准确描述检索树的基本特征
能够编程实现检索树的查找、插入、构造、删除算法（递归、非递归）

什么是检索树


检索树的特点

左小右大
中序有序

检索树的查找

检索树的查询效率取决于树的高度






检索树的插入和构造

插入原则：简单、保中序



检索树的删除

原则：仅删除要删除的结点，并且保持中序有序

检索树的结点的三种情况：没有儿子，有一个儿子，有两个儿子







平衡树

能够准确阐述平衡树的定义、性质
能够通过图示准确分析描述平衡树的插入、删除算法
能够准确图示给定平衡树的插入删除过程


哈夫曼树

用于哈夫曼编码，无损压缩数据

什么是哈夫曼树

如何构造哈夫曼树

哈夫曼算法实现

哈夫曼编译和译码

应用实例


图结构

准确复述图的基本概念和相关术语
理解邻接矩阵的物理含义
准确掌握图的存储方法

定义 


术语

顶点的度

子图

路径

回路：起点和终点相重合的简单路径
无向回路（圈）
有向回路
无向图的连通性



无向边

有向边

加权边

图的种类


邻接矩阵






散结构

如何利用高级语言描述存储结构

 数组可以用来描述顺序存储

一个数组元素便是一个存储结点
下标作为结点的存储地址
































{% endblock point1 %}